# 海盗
def pirate_package():
    # 定义载重容量
    capacity = 30
    # 货物重量列表
    goods = [3, 5, 4, 10, 7, 14, 2, 11]
    # 按重量升序排序
    goods.sort()

    # 已装载的重量和数量
    weight = 0
    count = 0

    # 贪心策略：每次选择重量最小的古董
    for item in goods:
        if weight + item <= capacity:
            print(f"装载古董重量: {item}")
            weight += item
            count += 1

    print(f"当前装载了 {count} 件古董！！！")

# 找零钱
def change_coins():
    # 准备硬币的面值
    faces = [25, 1, 5]
    # 总金额
    money = 41
    # 记录硬币的个数
    coins_num = 0

    # 按面值降序排序（贪心策略：优先使用大面值硬币）
    faces.sort(reverse=True)

    i = 0
    while i < len(faces):
        # 判断当前金额是否大于等于当前面值
        if money < faces[i]:
            i += 1
            continue
        # 使用当前面值的硬币
        money -= faces[i]
        print(f"使用硬币面值：{faces[i]}")
        coins_num += 1

    print(f"一共选择了 {coins_num} 个硬币！！")

# 背包
class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value
        self.value_den = value / weight  # 价值密度 = 价值 ÷ 重量

    def __repr__(self):
        return f"Item(重量={self.weight}, 价值={self.value}, 价值密度={self.value_den:.2f})"


# 贪心策略0-1背包 价值最大化
def pack_sack_method(items, comp_key):
    # 按照要求对货物进行排序
    sorted_items = sorted(items, key=comp_key, reverse=True)
    # 背包容量
    capacity = 150
    # 已装载的重量和价值
    weight = 0
    value = 0
    # 选择的物品列表
    selected = []

    for item in sorted_items:
        new_weight = weight + item.weight
        if new_weight <= capacity:
            selected.append(item)
            value += item.value
            weight = new_weight
            # 打印物品
            print(item)

    print(f"共选择了{len(selected)}件物品！！")
    print(f"总价值{value}")
    print(f"总重量是{weight}")
    print("------------------------------------")

# 程序入口
if __name__ == "__main__":
    # 海盗
    print("海盗问题：")
    pirate_package()
    print("------------------------------------")
    # 找零钱
    print("找零钱问题：")
    change_coins()
    print("------------------------------------")
    # 背包
    print("背包问题：")
    # 准备货物
    items = [
        Item(35, 10),
        Item(30, 40),
        Item(60, 30),
        Item(50, 50),
        Item(40, 35),
        Item(10, 40),
        Item(25, 30),
    ]

    # 价值主导
    print("价值主导的选择结果：")
    pack_sack_method(items, lambda x: x.value)

    # 重量主导
    print("重量主导的选择结果：")
    pack_sack_method(items, lambda x: -x.weight)

    # 价值密度主导
    print("价值密度主导的选择结果：")
    pack_sack_method(items, lambda x: x.value_den)